#include <boost/numeric/interval.hpp>

#include "Left_Turn.h"
#include "Adaptive_precision.h"

int simple_left_turn(const Point& a, const Point& b, const Point& c)
{
   double res = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
   double eps_mul = std::abs((b.x - a.x) * (c.y - b.y)) + std::abs((b.y - a.y) * (c.x - b.x));
   double filter = 8 * std::numeric_limits<double>::epsilon() * eps_mul;

   if (res > filter)
   {
      return 1;
   }

   if (-res > filter)
   {
      return -1;
   }

   return 0;
}

int interval_left_turn(const Point& a, const Point& b, const Point& c)
{
   boost::numeric::interval<double> bx(b.x), by(b.y);
   boost::numeric::interval<double> ax(a.x), ay(a.y);
   boost::numeric::interval<double> cx(c.x), cy(c.y);

   boost::numeric::interval<double> res = (bx - ax) * (cy - by) - (by - ay) * (cx - bx);
   
   if (res.lower() > 0)
   {
      return 1;
   }

   if (res.upper() < 0)
   {
      return -1;
   }

   return 0;
}

double adaptive_left_turn(const Point& a, const Point& b, const Point& c)
{
   double mult[12];
   std::pair<double, double> temp;
   temp = mul(b.x, c.y);
   mult[1] = temp.second;
   mult[0] = temp.first;
   
   temp = mul(-b.x, a.y);
   mult[3] = temp.second;
   mult[2] = temp.first;
   
   temp = mul(-a.x, c.y);
   mult[5] = temp.second;
   mult[4] = temp.first;

   temp = mul(-b.y, c.x);
   mult[7] = temp.second;
   mult[6] = temp.first;
   
   temp = mul(b.y, a.x);
   mult[9] = temp.second;
   mult[8] = temp.first;

   temp = mul(a.y, c.x);
   mult[11] = temp.second;
   mult[10] = temp.first;
    
    
   expansion_sum<2, 2>(mult, mult + 2);
   expansion_sum<2, 2>(mult + 4, mult + 6);
   expansion_sum<2, 2>(mult + 8, mult + 10);

   expansion_sum<4, 4>(mult, mult + 4);

   expansion_sum<8, 4>(mult, mult + 8);
    
   int result = get_sign<12>(mult);
    
   return result;
}

double left_turn(const Point& a, const Point& b, const Point& c)
{
   double result;
   
   result = simple_left_turn(a, b, c);
   if (result != 0) 
   {
      return result;
   }

   result = interval_left_turn(a, b, c);
   if (result != 0)
   {
      return result;
   }

   return adaptive_left_turn(a, b, c);
}
